package 优先算法.双指针.四数之和;
import java.util.*;
/**
 * <a href="https://leetcode.cn/problems/4sum/"
 */
public class  FourNum {
    public static void main(String[] args) {
        Solution so = new Solution();
        int[] nums = {-1000000000,-1000000000,1000000000,-1000000000,-1000000000};
        int target = 294967296;
        System.out.println(so.fourSum(nums, target));
    }
}
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //排序
        Arrays.sort(nums);
        //外侧基数
        for(int out=0;out<nums.length-3;) {
            if(target<0 && nums[0]>0)break;
            //内侧基数
            for(int in=out+1;in<nums.length-2;){

                //内侧和
                long sum =(long)target-nums[out]-nums[in];
                //双指针
                int left=in+1,right=nums.length-1;
                while(left < right){
                    if(nums[left]+nums[right]>sum){
                        right--;
                        while(left<right && nums[right+1]==nums[right]){
                            right--;
                        }
                    }else if(nums[left]+nums[right]<sum){
                        left++;
                        while(left<right && nums[left-1]==nums[right]){
                            left++;
                        }
                    }else{
                        List<Integer> list =Arrays.asList(nums[out],nums[in],nums[left],nums[right]);
                        result.add(list);
                        //保证不漏数
                        left++;
                        right--;
                        //去重中间重复
                        while(left<right && nums[right+1]==nums[right]){
                            right--;
                        }
                        while(left<right && nums[left-1]==nums[right]){
                            left++;
                        }
                    }
                }
                in++;
                //去重内基数
                while(in<nums.length-2 && nums[in-1]==nums[in]){
                    in++;
                }
            }
            out++;
            //去重外基数
            while(out<nums.length-3 && nums[out-1]==nums[out]){
                out++;
            }
        }
        return result;
    }
}